Digit DP
Given a huge integer N, you can use the dynamic programming algorithm to count up the number of things that satisfy the condition from non-negative integers less than or equal to N. Example of my implementation
DP S An integer between 1 and K, where the sum of each digit in decimal notation is a multiple of D. ABC154E An integer greater than or equal to 1 and less than or equal to N and exactly K non-zero numbers when expressed in decimal notation. Use the information about the upper i digits to find the information for i+1 digits
ABC154E: Let x be the number of cases where k non-zero numbers are used in the upper i digits. If the next digit is 0, it remains k, x ways; if 1 to 9, it becomes k+1, 9x ways.
code:python
for k in range(K + 1):
new_lessk += lessk # for 0 new_lessk + 1 += 9 * lessk # for 1..9 The only exception is when the upper i digits match N
1-9 could exceed N
Need to take care of the i+1st digit of N
The number of upper i digits matching N is always one way, so we have it by value, not by array.
Some of the explanations in the world make this an array too, but so far I haven't encountered a problem that requires it.
If the last case matching N satisfies the condition, answer +1.
If implemented naturally, the value is for "integers greater than or equal to 0", so depending on the problem conditions, the case of 0 is subtracted.
---
This page is auto-translated from /nishio/桁DP. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.